package day_6_28;

import java.util.ArrayList;
import java.util.List;

public class Main1 {
    /**
     * 57. 插入区间
     * https://leetcode.cn/problems/insert-interval/description/
     */
    public int[][] insert(int[][] intervals, int[] newInterval) {
        // 这个题存在三种情况：
        //1.某个intervals[0] > newInterval[1] 那么说明在当前的intervals位置的右侧是没有和其进行交集的，如果没有进行插入就插入到当前位置的前面
        //2.某个intervals[1] < newInterval[0] 那么说明在当前的intervals位置的左侧是没有和其进行交集的，
        //  那么就将newInterval插入到当前的后面的某个位置
        //3.存在交集的话，就进行计算 最小的左侧的值，计算最大右侧的值
        int left = newInterval[0];
        int right = newInterval[1];

        List<int[]> list = new ArrayList<>();
        boolean visit = false; // 进行判断 newInterval 数组数否进行插入了
        for(int[] interval : intervals) {
            int a = interval[0];
            int b = interval[1];
            if(a > right) {
                // 将其插入到当前的位置，如果没有插入过的话；之后将当前的interval再次进行插入
                if(!visit) {
                    list.add(new int[]{left,right});
                    visit = true;
                }
                list.add(interval);
            }else if(b < left) {
                list.add(interval);
            }else {
                left = Math.min(left,a);
                right = Math.max(right,b);
            }
        }

        // 判断是否插入，如果没有进行插入，说明应该插入到最后的位置
        if(!visit) {
            list.add(new int[]{left,right});
        }
        int[][] ret = new int[list.size()][2];
        for(int i = 0;i < list.size();i++) {
            ret[i] = list.get(i);
        }

        return ret;
    }
}
